package leetCode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * LCR 015. 找到字符串中所有字母异位词
 * https://leetcode.cn/problems/VabMRr/description/
 */
class Solution {
    //老师的版本
    public List<Integer> findAnagrams3(String ss, String pp) {
        List<Integer> ret = new ArrayList<>();
        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();
        int[] hash1 = new int[26];
        int[] hash2 = new int[26];
        int m = pp.length();
        //把p的字符全部存进hash2中
        for(char ch : p) hash2[ch - 'a']++;
        //用count表示有效字符的个数
        int count = 0;
        for(int left = 0, right = 0; right < ss.length(); right++) {
            //入窗口
            char in = s[right];
            //hash1[in - 'a']++;和下面的合并在一起了
            if(++hash1[in - 'a'] <= hash2[in - 'a']) count++;
            //判断
            if(right - left + 1 > m) {
                char out = s[left++];//left记得要++
                if(hash1[out - 'a']-- <= hash2[out - 'a']) count--;
                //出窗口
                //hash1[out - 'a']--;和上面的代码合并在一起了
            }
            //更新值
            if(count == m) {
                ret.add(left);
            }
        }
        return ret;
    }
    //true,自己的版本
    public List<Integer> findAnagrams2(String ss, String pp) {
        List<Integer> ret = new ArrayList<>();
        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();
        int[] hash1 = new int[26];
        int[] hash2 = new int[26];
        //把pp的值存放进哈希表里
        for(int i = 0; i < pp.length(); i++) {
            hash2[p[i] - 'a']++;
        }
        int m = pp.length();
        for(int left = 0, right = 0; right < ss.length(); right++) {
            //进窗口
            hash1[s[right] - 'a']++;
            //判断
            if(right - left + 1 > m) {
                //出窗口
                hash1[s[left] - 'a']--;
                left++;
            }
            //更新值
            if(right - left + 1 == m) {
                boolean flg = true;
//                for(int i = 0; i < m; i++) {
//                    if(hash2[p[i] - 'a'] != hash1[p[i] - 'a']) {
//                        flg = false;
//                        break;
//                    }
//                }
                //优化后的版本
                for(int i = 0; i < 25; i++) {
                    if(hash2[i] != hash1[i]) {
                        flg = false;
                        break;
                    }
                }
                if(flg) {
                    ret.add(left);
                }
            }
        }
        return ret;
    }
    //err
    public List<Integer> findAnagrams1(String ss, String pp) {
        List<Integer> ret = new ArrayList<>();
        char[] p = pp.toCharArray();
        char[] s = ss.toCharArray();
        Map<Character, Integer> mapP = new HashMap<>();
        Map<Character, Integer> mapS = new HashMap<>();
        //p先存进哈希表里
        for(int i = 0; i < pp.length(); i++) {
            mapP.put(p[i], mapP.getOrDefault(p[i], 0) + 1);
        }
        //滑动窗口
        for(int left = 0, right = 0; right < ss.length(); right++) {
            //进窗口
            mapS.put(s[right], mapS.getOrDefault(s[right], 0) + 1);
            //判断
            if(right - left + 1 > pp.length()) {
                //出窗口
                int n = mapS.get(s[left]);
                if(n == 1) {
                    mapS.remove(s[left]);
                    left++;
                } else {
                    mapS.put(s[left], mapS.get(s[left]) - 1);
                    left++;
                }
            }
            //更新值
            if(right - left + 1 == pp.length()) {
                boolean flg = true;
                for(int i = 0; i < pp.length(); i++) {
                    if(mapP.get(p[i]) != mapS.get(p[i])) {
                        flg = false;
                        break;
                    }
                }
                if(flg) {
                    //更新值
                    ret.add(left);
                }
            }
        }
        return ret;
    }
}